/**
 * 94. 二叉树的中序遍历.
 *
 * 【简单】
 *
 * 给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
 *
 * 示例 1：
 * 【https://assets.leetcode.com/uploads/2020/09/15/inorder_1.jpg】
 * 输入：root = [1,null,2,3]
 * 输出：[1,3,2]
 *
 * 示例 2：
 * 输入：root = []
 * 输出：[]
 *
 * 示例 3：
 * 输入：root = [1]
 * 输出：[1]
 */

import { TreeNode } from '../utils/tree'

// 递归
var inorderTraversal = function inorderTraversal(
	root: TreeNode | null
): number[] {
	const res: number[] = []

	function inorder(root) {
		if (!root) {
			return
		}
		inorder(root?.left)

		res.push(root.val)
		inorder(root.right)
	}

	inorder(root)
	return res
}

// 迭代
var inorderTraversal = function inorderTraversal(
	root: TreeNode | null
): number[] {
	const res: number[] = []
	const stack: Array<TreeNode | null> = []
	while (root || stack.length) {
		while (root) {
			stack.push(root)
			root = root.left
		}
		root = stack.pop()!
		res.push(root!.val)
		root = root!.right
	}

	return res
}
